package com.coder.algorithm.leetcode

/**
 * [119. 杨辉三角 II](https://leetcode-cn.com/problems/pascals-triangle-ii/)
 *
 * @author yuhus
 * @date: 2022/3/29
 */
object l_0119 {

    /**
     * 使用一个数组
     * 第 i+1 行的 j 列只用到的第 i 行的第 j-1 和 j 的数据，所以可以倒着计算行
     */
    fun getRow(rowIndex: Int): List<Int> {
        var pre = ArrayList<Int>()
        // 第i行 有 i+1 个元素，坐标 [0,i]
        for (i in 0..rowIndex) {
            pre.add(0)
            for (j in i downTo  0) {
                if (j == 0 || j == i) {
                    pre[j] = 1
                } else {
                    pre[j] = pre[j - 1] + pre[j]
                }
            }
        }
        return pre
    }

    /**
     * 滚动数组，第 i+1 行的计算仅用到了第 i 行的数据
     */
    fun getRow_1(rowIndex: Int): List<Int> {
        var pre = ArrayList<Int>()
        // 第i行 有 i+1 个元素，坐标 [0,i]
        for (i in 0..rowIndex) {
            val cur = ArrayList<Int>()
            for (j in 0..i) {
                if (j == 0 || j == i) {
                    cur.add(1)
                } else {
                    cur.add(pre[j - 1] + pre[j])
                }
            }
            pre = cur
        }
        return pre
    }
}